内田 3章 整列集合と選択公理
例
$ (\N,\le)は整列集合だが、$ (\Z,\le),(\Bbb{Q},\le),(\R,\le)は整列集合でない 整列集合$ (X,\le)に対して$ X\langle\bullet\rangle:X\ni a\mapsto\{x\in X\mid x<a\}\in2^Xを$ aによる切片と呼ぶ $ X_{< a}とも書ける
以後こちらを使うtakker.icon
定理9.1
任意の整列集合$ (X,\le)について、$ \forall\phi:X\to Xが単射な単調増加写像なら、$ \forall x\in X:x\le\phi(x)である 証明
$ \iff\forall x,y\in X:(x\le y\implies\phi(x)\le\phi(y))\land\forall x,y\in X:(\phi(x)=\phi(y)\implies x=y)
$ \iff \forall x\in X:(x\le\phi(x)\lor\phi(x)<x)\land\forall x,y\in X:(x\le y\implies\phi(x)\le\phi(y))\land\forall x,y\in X:(\phi(x)=\phi(y)\implies x=y)
$ \because整列集合の定義
$ \implies\forall x\in X:(x\le\phi(x)\lor\phi^2(x)<\phi(x))\land\forall x,y\in X:(x\le y\implies\phi(x)\le\phi(y))\land\forall x,y\in X:(\phi(x)=\phi(y)\implies x=y)
うーん、これだとうまくいかないか
空でない$ Xの部分集合を得られるので、それを整列集合の条件に代入して無限降下列を作り、矛盾を示す $ \lnot\forall x\in X:x\le\phi(x)
$ \iff\exist x\in X:x>\phi(x)
$ \implies\exist m\in\{x\in X\mid x>\phi(x)\}\forall x\in\{x\in X\mid x>\phi(x)\}:x\ge m
$ \iff\exist m\in X:m>\phi(m)\land\forall x\in X:(x>\phi(x)\implies x\ge m)
$ \implies\exist m\in X:m>\phi(m)\land\phi(m)>\phi^2(m)\land\phi(m)>\phi^2(m)\implies\phi(m)\ge m)
$ \because$ \phiの単調増加性
$ \iff\exist m\in X:\phi(m)\ge m>\phi(m)>\phi^2(m)
$ \iff\bot
$ \underline{\therefore\forall x\in X:x\le\phi(x)\quad}_\blacksquare
問9.1 任意の整列集合$ (X,\le)にて$ \forall a\in X\forall b\in X_{<a}:{X_{<a}}_{<b}=X_{<b}が成り立つ 自明すぎるので略takker.icon
問9.2
1. $ (X,\le)\cong(X_{<a},\le)となるような整列集合$ (X,\le)と$ a\in Xは存在しない
$ \congは順序同型のことtakker.icon 2. $ (X_{<a},\le)\cong(X_{<b},\le)となるような整列集合$ (X,\le)と$ a,b\in X\land a\neq bは存在しない
問9.3 任意の整列集合$ (X,\le),(Y,\le)と順序同型写像$ f:X\to Yにて$ \forall a\in X:f^\to(X_{<a})=Y_{<f(a)}が成り立つ 定理9.2 任意の整列集合$ (X,\le),(Y,\le)にて以下が成り立つ $ \exist Z:\begin{dcases}Z=\{a\in X\mid\exist b\in Y:(X_{<a},\le)\cong(Y_{<b},\le)\}\\Z=X\lor \exist a\in X:Z=X_{<a}\end{dcases}
任意の整列集合$ (X,\le),(Y,\le)にて1,2,3のいずれかただ1つが成り立つ 1. $ (X,\le)\cong(Y,\le)
2. $ \exist a\in X:(X_{<a},\le)\cong(Y,\le)
3. $ \exist b\in Y:(X,\le)\cong(Y_{<b},\le)
$ \forall\Lambda,\mathcal X\forall A:\Lambda\to\mathcal Xにて、$ A:\Lambda\to\mathcal Xの直積を $ \prod A:=\left\{f:\Lambda\to\bigcup_{\lambda\in\Lambda}A(\lambda)\middle|\forall\lambda\in\Lambda:f(\lambda)\in A(\lambda)\right\}
と定義する
$ \Lambda=\Nとすれば、$ (A_0,A_1,\cdots,A_n)を函数$ \N\to\bigcup_{i\in\N}A_iとみなせる
$ \Lambdaが非可算集合など、任意の集合でも成立するように定義すると、上記の様になる
$ \Lambda=\{i,j\}のとき、$ \prod A=\left\{f:\{i,j\}\to A(i)\cup A(j)\middle|f(i)\in A(i)\land f(j)\in A(j)\right\}となる
$ \forall\Lambda,\mathcal X\forall A:\Lambda\to\mathcal X\setminus\{\varnothing\}:\prod A\neq\varnothing
$ p_\bullet:\Lambda\ni\lambda\mapsto\left(\prod A\ni f\mapsto f(\lambda)\in A(\lambda)\right)\in(2^{\prod A}\to2^{\bigcup_{\lambda\in\Lambda} A(\lambda)})を射影と呼ぶ $ \forall A,Bにて、$ \prod(f:1\mapsto A,2\mapsto B)を$ A\times Bと略記する
定理13.6 任意の整列集合$ (X,\le)にて$ \forall x\in X_{\neq\max}\exist !y\in X:x\lessdot y
$ X_{\neq\max}:=\{x\in X\mid X_{> x}\neq\varnothing\}：$ Xから(もし存在すれば)最大元を除いた集合
証明
$ \min X_{>x}が$ xの後続元になることを示す ここから$ x\in X_{\neq\max}の後続元を$ x^+:=\min X_{>x}と表記する 定理13.7 任意の整列集合$ (X,\le)と狭義単調増加写像$ f:X\rightarrowtail Xにて$ \forall x\in X:x\le f(x) 証明
$ \exist x\in X:f(x)<x
$ \implies\exist m\in\{x\in X\mid f(x)<x\}\forall x\in X:f(x)<x\implies m\le x
$ \iff\exist m\in X:\begin{dcases} f(m)<m\\\forall x\in X:f(x)<x\implies m\le x\end{dcases}
$ \iff\exist m\in X:\begin{dcases} f(m)<m\\\forall x\in X_{<m}:x\le f(x)\end{dcases}
$ \implies\exist m\in X:\begin{dcases}f^2(m)<f(m)\\\forall x\in X_{<m}:x\le f(x)\end{dcases}
$ \implies\exist m\in X:\begin{dcases}f^2(m)<f(m)\\f(m)\le f^2(m)\end{dcases}
$ \implies\bot
$ \underline{\therefore\forall x\in X:x\le f(x)\quad}_\blacksquare
$ \forall m\in X:
$ \forall x\in X_{<m}:x\le f(x)
$ \implies(f(m)<m\implies f(m)\le f^2(m))
$ \implies(f(m)<m\implies f(m)\le f^2(m)< f(m))
$ \implies(f(m)<m\implies\bot)
$ \implies m\le f(m)
$ \implies\forall m\in X:(\forall x\in X_{<m}:x\le f(x))\implies m\le f(m)
$ \implies\forall x\in X:x\le f(x)
$ X\Braket{a}:=X_{<a}=\{x\in X\mid x<a\}
$ aによる切片という
$ X\Braket{a}がよく使われる
補題13.9
定理13.10
補題13.11
補題13.12
補題13.13